package 面试超级高频;

import 其他.DataStructure.TreeNode;
import MyUtils.MHUtils;
import org.junit.Test;

import java.util.*;

/*
    做完题一定写入表格

    需要背所需变量：记住一个oldsize和初始rot
    之后正常理解写
*/
public class 二叉树的锯齿形层序遍历103 {
    @Test
    public void test() {
        TreeNode rot = MHUtils.strToTree("3,9,20,null,null,15,7");
        System.out.println(MHUtils.cengxu(rot));
        System.out.println(zigzagLevelOrder(rot));
    }
/*
    评论 边界他们累不？
*/
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if(root==null){
//            return null;
            //返回结果为String可以直接“”
            //但如果是List<>,空时要return new
            return new ArrayList<>();
        }
        List<List<Integer>> res = new ArrayList<>();
        //初始rot放入32,看图
       List<Integer> rotTmp  = new ArrayList<>();
       rotTmp.add(root.val);
//        res.add(new ArrayList<>(root.val));
        res.add(rotTmp);

        //自己不放心
        if(root.left==null && root.right==null){
            return res;
        }
        Queue<TreeNode> que = new LinkedList<>();
        if(root.left!=null) {
            que.add(root.left);
        }
        if(root.right!=null){
            que.add(root.right);
        }
        int oldSize = que.size();
        int f=0;
        while(oldSize > 0){
            List<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < oldSize; i++) {
                TreeNode poll = que.poll();
                //看图,这里少了
                tmp.add(poll.val);
                //可能有跳跃null，不是完全二叉
                if(poll==null){
                    //resstr不打印东西
                }else{
                    if(poll.left!=null){
                        que.add(poll.left);
                    }
                    if(poll.right!=null){
                        que.add(poll.right);
                    }
                }
            }
            //后退一级记录oldSize,因为要一整行完事
            oldSize = que.size();
            //先反转，因为rot本身占向右一级
            if(f==0){
                Collections.reverse(tmp);
                res.add(tmp); f=1;
            }else if(f==1){
                res.add(tmp); f=0;
            }
        }

        return res;
    }
}
